/**
 * cstring.h
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdarg.h>
#include "cstring.h"

#ifndef GCC_LIKELY
#define GCC_LIKELY(x) __builtin_expect(!!(x), 1)
#endif
#ifndef GCC_UNLIKELY
#define GCC_UNLIKELY(x) __builtin_expect(!!(x), 0)
#endif

#ifndef __always_inline
#define __always_inline __inline __attribute__ ((__always_inline__))
#endif

#define FORMAT_TEMP_SIZE 1024

#define INTERNING_POOL_SIZE 1024

/* HASH_START_SIZE must be 2 pow */
#define HASH_START_SIZE 16

struct string_node
{
    struct cstring_data data;
    char buffer[CSTRING_INTERNING_SIZE];
    struct string_node* next;
} CSTRING_ALIGN16;

struct string_pool
{
    struct string_node node[INTERNING_POOL_SIZE];
} CSTRING_ALIGN16;

struct string_interning
{
    int lock;
    int size;
    struct string_node** hash;
    struct string_pool* pool;
    int index;
    int total;
} CSTRING_ALIGN16;

static struct string_interning GS;

static inline void lock_gs()
{
    while (__sync_lock_test_and_set(&(GS.lock), 1)) {
        ;
    }
}

static inline void unlock_gs()
{
    __sync_lock_release(&(GS.lock));
}

__always_inline void insert_node(struct string_node** hash, int sz, struct string_node* n)
{
    uint32_t h = n->data.hash_size;
    int index = h & (sz - 1);
    n->next = hash[index];
    hash[index] = n;
}

__always_inline void expand(struct string_interning* si)
{
    int new_size = si->size << 1;
    if (new_size < HASH_START_SIZE) {
        new_size = HASH_START_SIZE;
    }
    assert(new_size > si->total);
    struct string_node** new_hash = malloc(sizeof(struct string_node*) * new_size);
    __builtin_memset(new_hash, 0, sizeof(struct string_node*) * new_size);
    int i;
    for (i = 0; i < si->size; i++) {
        struct string_node* node = si->hash[i];
        while (node) {
            struct string_node* tmp = node->next;
            insert_node(new_hash, new_size, node);
            node = tmp;
        }
    }
    free(si->hash);
    si->hash = new_hash;
    si->size = new_size;
}

static cstring interning(struct string_interning* si, const char* cstr, size_t sz, uint32_t hash)
{
    if (si->hash == NULL) {
        return NULL;
    }
    int index = (int) (hash & (si->size - 1));
    struct string_node* n = si->hash[index];
    while (n) {
        if (n->data.hash_size == hash) {
            if (__builtin_strcmp(n->data.cstr, cstr) == 0) {
                return &n->data;
            }
        }
        n = n->next;
    }
    /* 80% (4/5) threshold */
    if (si->total * 5 >= si->size * 4) {
        return NULL;
    }
    if (si->pool == NULL) {
        /* need not free pool */
        si->pool = malloc(sizeof(struct string_pool));
        assert(si->pool);
        if (!si->pool) {
            perror("cstring error: lack of memory when interning!\n");
            return NULL;
        }
        si->index = 0;
    }
    n = &si->pool->node[si->index++];
    __builtin_memcpy(n->buffer, cstr, sz);
    n->buffer[sz] = '\0';

    cstring cs = &n->data;
    cs->cstr = n->buffer;
    cs->hash_size = hash;
    cs->type = CSTRING_INTERNING;
    cs->ref = 0;
    n->next = si->hash[index];
    si->hash[index] = n;

    return cs;
}

__always_inline cstring cstring_interning(const char* cstr, size_t sz, uint32_t hash)
{
    cstring ret;
    lock_gs();
    ret = interning(&GS, cstr, sz, hash);
    if (ret == NULL) {
        expand(&GS);
        ret = interning(&GS, cstr, sz, hash);
    }
    ++GS.total;
    unlock_gs();
    assert(ret);
    return ret;
}

__always_inline uint32_t hash_blob(const char* buffer, size_t len)
{
    const uint8_t* ptr = (const uint8_t*)buffer;
    size_t h = len;
    size_t step = (len >> 5) + 1;
    size_t i;
    for (i = len; i >= step; i -= step) {
        h = h ^ ((h << 5) + (h >> 2) + ptr[i - 1]);
    }
    return (h == 0) ? 1 : h;
}

void cstring_free_persist(cstring s)
{
    if (s->type == CSTRING_PERMANENT) {
        free(s);
    }
}

__always_inline cstring cstring_clone(const char* cstr, size_t sz)
{
    if (sz < CSTRING_INTERNING_SIZE) {
        return cstring_interning(cstr, sz, hash_blob(cstr, sz));
    }
    struct cstring_data* p = malloc(sizeof(struct cstring_data) + sz + 1);
    assert(p);
    if (!p) {
        return NULL;
    }
    void* ptr = (void*)(p + 1);
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    __builtin_memcpy(ptr, cstr, sz);
    ((char*)ptr)[sz] = '\0';
    p->hash_size = 0;
    return p;
}

cstring cstring_persist(const char* cstr, size_t sz)
{
    cstring s = cstring_clone(cstr, sz);
    if (s->type == 0) {
        s->type = CSTRING_PERMANENT;
        s->ref = 0;
    }
    return s;
}

cstring cstring_grab(cstring s)
{
    if (s->type & (CSTRING_PERMANENT | CSTRING_INTERNING)) {
        return s;
    }
    if (s->type == CSTRING_ONSTACK) {
        cstring tmp = cstring_clone(s->cstr, s->hash_size);
        return tmp;
    }
    else {
        if (s->ref == 0) {
            s->type = CSTRING_PERMANENT;
        }
        else {
            __sync_add_and_fetch(&s->ref, 1);
        }
        return s;
    }
}

void cstring_release(cstring s)
{
    if (s->type != 0) {
        return;
    }
    if (s->ref == 0) {
        return;
    }
    if (__sync_sub_and_fetch(&s->ref, 1) == 0) {
        free(s);
    }
}

uint32_t cstring_hash(cstring s)
{
    if (s->type == CSTRING_ONSTACK) {
        return hash_blob(s->cstr, s->hash_size);
    }
    if (s->hash_size == 0) {
        s->hash_size = hash_blob(s->cstr, strlen(s->cstr));
    }
    return s->hash_size;
}

int cstring_equal(cstring a, cstring b)
{
    if (a == b) {
        return 1;
    }
    if ((a->type == CSTRING_INTERNING) &&
        (b->type == CSTRING_INTERNING)) {
        return 0;
    }
    if ((a->type == CSTRING_ONSTACK) &&
        (b->type == CSTRING_ONSTACK)) {
        if (a->hash_size != b->hash_size) {
            return 0;
        }
        return __builtin_memcmp(a->cstr, b->cstr, a->hash_size) == 0;
    }
    uint32_t hasha = cstring_hash(a);
    uint32_t hashb = cstring_hash(b);
    if (hasha != hashb) {
        return 0;
    }
    return __builtin_strcmp(a->cstr, b->cstr) == 0;
}

static inline cstring cstring_cat2(const char* a, const char* b)
{
    size_t sa = strlen(a);
    size_t sb = strlen(b);
    if (sa + sb < CSTRING_INTERNING_SIZE) {
        char tmp[CSTRING_INTERNING_SIZE];
        __builtin_memcpy(tmp, a, sa);
        __builtin_memcpy(tmp + sa, b, sb);
        tmp[sa + sb] = '\0';
        return cstring_interning(tmp, sa + sb, hash_blob(tmp, sa + sb));
    }
    struct cstring_data* p = malloc(sizeof(struct cstring_data) + sa + sb + 1);
    assert(p);
    if (!p) {
        return NULL;
    }
    char* ptr = (char*) (p + 1);
    p->cstr = ptr;
    p->type = 0;
    p->ref = 1;
    __builtin_memcpy(ptr, a, sa);
    __builtin_memcpy(ptr + sa, b, sb);
    ptr[sa + sb] = '\0';
    p->hash_size = 0;
    return p;
}

cstring cstring_cat(cstring_buffer sb, const char* str)
{
    cstring s = sb->data;
    if (s->type == CSTRING_ONSTACK) {
        int i = (int) s->hash_size;
        while (i < CSTRING_STACK_SIZE - 1) {
            s->cstr[i] = *str;
            if (*str == '\0') {
                return s;
            }
            ++s->hash_size;
            ++str;
            ++i;
        }
        s->cstr[i] = '\0';
    }
    cstring tmp = s;
    sb->data = cstring_cat2(tmp->cstr, str);
    cstring_release(tmp);
    return sb->data;
}

static cstring cstring_format(const char* format, va_list ap)
{
    static char* cache = NULL;
    char* result;
    char* temp = cache;
    if (temp) {
        temp = __sync_val_compare_and_swap(&cache, temp, NULL);
    }
    if (temp == NULL) {
        if (!(temp = (char*)malloc(FORMAT_TEMP_SIZE))) {
            return NULL;
        }
    }
    int n = vsnprintf(temp, FORMAT_TEMP_SIZE, format, ap);
    if (n >= FORMAT_TEMP_SIZE) {
        int sz = FORMAT_TEMP_SIZE << 1;
        while (1) {
            if (!(result = malloc(sz))) {
                return NULL;
            }
            n = vsnprintf(result, sz, format, ap);
            if (n >= sz) {
                free(result);
                sz <<= 1;
            }
            else {
                break;
            }
        }
    }
    else {
        result = temp;
    }
    cstring r = (cstring)malloc(sizeof(struct cstring_data) + n + 1);
    assert(r);
    if (!r) {
        return NULL;
    }
    r->cstr = (char*)(r + 1);
    r->type = 0;
    r->ref = 1;
    r->hash_size = 0;
    __builtin_memcpy(r->cstr, result, n + 1);
    if (temp != result) {
        free(result);
    }
    if (!__sync_bool_compare_and_swap(&cache, NULL, temp)) {
        free(temp);
    }

    return r;
}

cstring cstring_vprintf(cstring_buffer sb, const char* format, ...)
{
    cstring s = sb->data;
    va_list ap;
    va_start(ap, format);
    if (s->type == CSTRING_ONSTACK) {
        int n = vsnprintf(s->cstr, CSTRING_STACK_SIZE, format, ap);
        if (n >= CSTRING_STACK_SIZE) {
            s = cstring_format(format, ap);
            sb->data = s;
        }
        else {
            s->hash_size = n;
        }
    }
    else {
        cstring_release(sb->data);
        s = cstring_format(format, ap);
        sb->data = s;
    }
    va_end(ap);
    return s;
}



